package 每日一题OJ;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author shy_black
 * @date 2019/8/21 11:56
 * @Description:
 * 1.排序
 * 2.遍历数组
 * 2.1.去重，如果nums[i]>0，break
 * 2.2.while循环，找i+l+r== 0的数，去重，加到list中
 * 3.返回
 *
 */
public class _15_三数之和 {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            List<Integer> list = new ArrayList<>();
            if(nums.length <3)
                return res;
            Arrays.sort(nums);
            for(int i = 0;i < nums.length;i++) {
                if(nums[i] > 0) {
                    break;
                }
                //去重
                if(i>0 && nums[i] == nums[i-1])
                    continue;
                int l = i + 1;
                int r = nums.length - 1;

                while(l < r) {
                    int tmp = nums[l] + nums[i] + nums[r];
                    if(tmp == 0) {
                        res.add(Arrays.asList(nums[i],nums[l],nums[r]));
                        //去重
                        while( l < r && nums[l] == nums[l+1] ) l++;
                        while( l < r && nums[r] == nums[r-1] ) r--;
                        l++;
                        r--;
                    }else if(tmp > 0) {
                        r--;
                    }else if(tmp < 0) {
                        l++;
                    }


                }

            }
            return res;
        }

    }